It is well known to perform interleaving of data in a communications system using forward error correction (FEC) in order, on deinterleaving, to distribute errors to facilitate their correction. Typically, such interleaving uses a block interleaver to interleave blocks of data. So-called turbo coding (parallel concatenated convolutional coding) uses an interleaver between inputs to two convolutional coders which produce respective parity bits from the input data before and after interleaving. With increasing attention being given to the use of turbo coding, particularly in wireless communications systems, attention has also been given to the form of the interleaver.
So-called 3rd generation CDMA (code division multiple access) wireless communications systems are also being developed which require a channel or inter-frame interleaver which operates to interleave or permute data in blocks corresponding to the radio frame duration, typically 10 ms. In such systems the channel interleaver either precedes or follows a rate matching function which serves to match various data rates to the radio frame rate, and which typically involves puncturing (omission) or repetition of data symbols, in this case data bits. It is desirable to distribute the omitted or repeated bits as evenly as possible, with as great a distance as possible between punctured or repeated bits in the de-interleaved frames, in a manner that is easy to implement and that is relatively independent of variables such as the frame-size, number of frames, and puncturing rate.
The present invention is concerned with rate matching in a manner which can be used with particular advantage for data after channel interleaving as described and claimed in the related application referred to above, but which is also applicable to other forms of interleaved data. This invention also provides improvements in and further applications of such channel interleaving.
According to one aspect, this invention provides a method of matching a rate of data bits, in a matrix of data bits interleaved by a predetermined interleaving process, to a desired rate by deletion of redundant data bits or repetition of data bits derived from the matrix, including the steps of: determining in a non-interleaved-matrix of said data bits a pattern of bits to be deleted or repeated to provide said desired data rate; decoding an address of each bit in said pattern in a manner inverse to the interleaving process to produce a respective address of the bit in the matrix of interleaved data bits; and deleting or repeating the respective bit in the interleaved data bits in dependence upon the respective address.
It is particularly advantageous, and may be necessary in practice, for the address decoding to be performed in the same manner as a coding of addresses for producing the interleaved data bits from the non-interleaved matrix of said data bits. This is facilitated in preferred embodiments of the method of the invention by the interleaving process comprising permuting rows and columns of a matrix of Nr rows and Nc columns, in which data bits to be interleaved are represented row by row, in accordance with:
Row Permutation Ir(k)=[xcex1rk+fc(l)]modNr
Column Permutation Ic(l)=[xcex1cl+fr(k)]modNc
where Ir(k) represents a data bit with a row index k, k is an integer from 1 to Nr, xcex1r is an integer, fc(l) is a non-zero function of a column index l, l is an integer from 1 to Nc, Ic(l) represents a data bit with the column index l, xcex1c is an integer, fr(k) is zero or a function of the row index k, and modNr and modNc represent modulo-Nr and modulo-Nc arithmetic respectively, interleaved data bits being derived from the matrix column by column.
It is currently considered optimum to choose fc(l)=ml+[Nr+1]mod2, where m is an integer, m approximately equal to Nr/Nc, fr(k)=2k+[Nc+1]mod2, and xcex1r as the largest prime number less than Nr/log2(log2(Nr)).
The invention also provides rate matching apparatus arranged for carrying out a method as recited above.
Another aspect of this invention provides a method of interleaving data bits comprising permuting rows and columns of a matrix of Nr rows and Nc columns, in which data bits to be interleaved are represented row by row, in accordance with:
xe2x80x83Row Permutation Ir(k)=[xcex1rk+fc(l)]modNr
Column Permutation Ic(l)=[xcex1cl+fr(k)]modNc
where Ir(k) represents a data bit with a row index k, k is an integer from 1 to Nr, xcex1r is an integer, fc(l)=ml+[Nr+1]mod2 is a non-zero function of a column index l, l is an integer from 1 to Nc, m is an integer, Ic(l) represents a data bit with the column index l, xcex1c is an integer, fr(k)=2k+[Nc+1]mod2, and mod2, modNr and modNc represent modulo-2, modulo-Nr, and modulo-Nc arithmetic respectively, interleaved data bits being derived from the matrix column by column.
The invention also provides a data interleaver arranged for carrying out this method.
Another aspect of the invention provides a method of interleaving and rate matching parallel concatenated convolutional coded data by deletion of coded data bits, the coded data bits comprising systematic bits and parity bits, including the steps of interleaving the systematic bits separately from the parity bits, and deleting parity bits from the interleaved parity bits to provide the rate matching.
A further aspect of the invention provides a method of interleaving and rate matching parallel concatenated convolutional coded data by repetition of coded data bits, the coded data bits comprising systematic bits and parity bits, including the steps of interleaving the systematic bits separately from the parity bits, and repeating parity bits of the interleaved parity bits with a greater repetition factor than any repetition of systematic bits of the interleaved systematic bits, to provide the rate matching.
The invention further provides coding, interleaving, and rate matching apparatus arranged to carry out these methods.
Yet another aspect of this invention relates to a method of shuffling interleaved and rate matched data streams in the manner described below with reference to FIG. 4 of the drawings, and to the recursive application of this method to more than two such data streams.